package ru.susu.algebra.methods.simplex;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import ru.susu.algebra.methods.IMathMethod;
import ru.susu.algebra.methods.simplex.exceptions.SimplexException;
import ru.susu.algebra.util.StringUtilities;
import ru.susu.algebra.wrapper.number.BigIntegerFraction;

/**
 * n - число переменных
 * m - число ограничений
 * В нулевом столбце матрицы стоят правые части
 *
 * Решаем задачу: Ax=b, причем x>=0
 *
 * Стоит смотреть: Глебов "Методы оптимизации" стр 19
 *
 * @author akargapolov
 * @since: 08.06.2009
 */
public class SimplexMethod implements IMathMethod<List<BigIntegerFraction>>
{
	private List<BigIntegerFraction>[] _matrix;
	private int _rows;	//количество ограничений
	private int _columns;	//количество столбцов
	private int _startFakeColumn;	//начальный индекс введенных переменных во время поиска начального плана
	private BigIntegerFraction[] _function;
	private int[] _basis;

	public static boolean _debug = false;

	/**
	 * @param sources
	 */
	@Override
	public List<BigIntegerFraction> run(Object... sources) throws SimplexException
	{
		initialize(sources);
		int resultLength = _columns - 1;
		if (!findFirstPlan())
		{
			throw new SimplexException(false);
		}
		List<BigIntegerFraction> result = new ArrayList<BigIntegerFraction>();
		Collections.addAll(result, createFractionsArray(resultLength + 1, BigIntegerFraction.ZERO));
		for (int index = 0;index < _basis.length;index++)
		{
			if (_basis[index] >= result.size())
				//игнорируем введенные нулевые переменные
				continue;
			result.set(_basis[index], _matrix[index].get(0));
		}
		return result;
	}

	@SuppressWarnings("unchecked")
	protected void initialize(Object... sources)
	{
		Integer[][] matrix = (Integer[][]) sources[0];
		_rows = matrix.length;
		_columns = matrix[0].length;

		_matrix = (List<BigIntegerFraction>[]) Array.newInstance(List.class, _rows);
		for (int i = 0; i < _rows; i++)
		{
			_matrix[i] = new ArrayList<BigIntegerFraction>();
			for (int j = 0; j < _columns; j++)
			{
				_matrix[i].add(new BigIntegerFraction(matrix[i][j]));
			}
		}
		_function = createFractionsArray(_columns - 1, BigIntegerFraction.ZERO);
		Integer[] function = (Integer[]) sources[1];
		for (int i = 0; i < function.length; i++)
		{
			_function[i] = new BigIntegerFraction(function[i]);
		}
	}

	private void addColumn2Matrix(int index4Value, BigIntegerFraction value)
	{
		for (int i = 0;i<_rows;i++)
		{
			if (i == index4Value)
			{
				_matrix[i].add(value);
			}
			else
			{
				_matrix[i].add(BigIntegerFraction.ZERO);
			}
		}
		_columns++;
	}

	private void addRow2Matrix(BigIntegerFraction value)
	{
		_matrix = Arrays.copyOf(_matrix, _rows + 1);
		_matrix[_rows] = new ArrayList<BigIntegerFraction>();
		Collections.addAll(_matrix[_rows], createFractionsArray(_columns, value));
		_rows++;
	}

	private  BigIntegerFraction[] createFractionsArray(int size, BigIntegerFraction value)
	{
		BigIntegerFraction[] result = new BigIntegerFraction[size];
		Arrays.fill(result, value);
		return result;
	}

	/**
	 * Добавляем новые переменные, которые затем попадут в базис, и которые мы будем выводить при
	 * помощи максимизации их отрицательной суммы.
	 */
	protected void createSimpleBasis()
	{
		v = new ArrayList<Integer>();

		_basis = new int[_rows - 1];

		int oldColumns = _columns;
		for(int i=0; i<_rows - 1; i++)
		{
			if (_matrix[i].get(0).compareTo(BigIntegerFraction.ZERO) >= 0)
			{
				addColumn2Matrix(i, BigIntegerFraction.ONE);
				_basis[i] = _matrix[i].size() - 1;
				for (int j = 0; j < oldColumns; j++)
				{
					_matrix[_rows - 1].set(j, _matrix[_rows - 1].get(j).subtract(_matrix[i].get(j)));
				}
			}
			else
			{
				throw new RuntimeException("Works only for positive right parts");
				/*
				for (int j=0;j<=n;j++)
				{
					_matrix[i].set(j, _matrix[i].get(j).multiply(BigIntegerFraction.MINUS_ONE));
				}
				addColumn2Matrix(i, BigIntegerFraction.MINUS_ONE);
				v.add(i);*/
			}
		}
	}


	protected boolean findFirstPlan() throws SimplexException
	{
		_startFakeColumn = _columns;
		while (true)
		{
			List<BigIntegerFraction>[] _startMatrix = getMatrixCopy();
			addRow2Matrix(BigIntegerFraction.ZERO);
			// добавим строку с дельтами, см Большакова стр 26
			createSimpleBasis();
			// workWithNegatives();
			try
			{
				printMatrix();
				doIterations();
			}
			catch (SimplexException e)
			{
				if (e.isSolutionFound())//дельты не отрицательны
				{
					List<Integer> fakes = getFakeBasisColumns();
					if (isAllColumnValuesZero(fakes, 0))//все переменные выведены из базиса или невыведенные обнулены
					{
						return _matrix[_rows - 1].get(0).equals(BigIntegerFraction.ZERO);//целевая функция должна быть 0
					}
					//выводим фейки - фейковые строки являются зависимыми от остальных
					_matrix = _startMatrix;
					_rows = _matrix.length;_columns=_matrix[0].size();
					_matrix = getMatrixCopy(fakes.toArray(new Integer[fakes.size()]));
					_rows = _matrix.length;
				}
				else
				{
					return false;
				}
			}
			if (_matrix.length == 0)
			{
				throw new RuntimeException("I don't know about this situation!!! Matrix is empty!!! Panic!!");
			}
		}
	}

	protected void doIterations() throws SimplexException
	{
		while(true)
		{
			int chosenColumn = chooseColumn();
			int chosenRow = chooseRow(chosenColumn);
			simpleChangeBasis(chosenRow, chosenColumn);
			if (_debug)
			{
				System.out.println("Chose: " +  chosenRow + " , " + chosenColumn);
				printMatrix();
				System.out.println("Basis: " + Arrays.toString(_basis));
			}
		}
	}

	protected int chooseColumn() throws SimplexException
	{
		int result = -1;
		BigIntegerFraction tmpZ = BigIntegerFraction.ZERO;

		for (int j = 1;j<_columns;j++)
		{
			BigIntegerFraction currentZ = _matrix[_rows-1].get(j);
			if (tmpZ.compareTo(currentZ) > 0)
			{
				tmpZ  = currentZ;
				result = j;
			}
		}

		if (result == -1)
		{
			throw new SimplexException(true);
		}

		return result;
	}

	/**
	 * Выбираем строку с минимальным отношением z_i0 / z_is, где z_is > 0
	 *
	 * @param chosenColumn уже выбранный столбец
	 * @return строка, которую нужно выюрать на данном шаге
	 * @throws SimplexException если все элементы столбца не положительны, то решения не существует
	 */
	protected int chooseRow(int chosenColumn) throws SimplexException
	{
		int result = -1;
		BigIntegerFraction tmpValue = null;
		for(int row=0; row<_rows; row++)
		{
			//игнорируем не положительные значения
			if(_matrix[row].get(chosenColumn).compareTo(BigIntegerFraction.ZERO) <= 0)
			{
				continue;
			}
			BigIntegerFraction t = _matrix[row].get(0).divide(_matrix[row].get(chosenColumn));	//a[i][0] / a[i][j]
			if (tmpValue == null || tmpValue.compareTo(t) > 0)
			{
				tmpValue = t;
				result = row;
			}
		}
		if (tmpValue == null)
		{
			throw new SimplexException(false); //решения не существует, целевая функция не ограничена
		}
		return result;
	}

	/**
	 * Производит пересчет матрицы. Вводит нужную переменную в базис. <br>
	 * В выбранном столбце будут нули и одна единица. Остальные значения пересчитываются по
	 * приведенным формулам. <br>
	 *
	 * Если  i!= r, то a_i = a_i - z_is/z_rs*a_r, <br>
	 * иначе a_r = a_r / z_rs
	 *
	 * @param chosenRow
	 * @param chosenColumn
	 */
	protected void simpleChangeBasis(int chosenRow, int chosenColumn)
	{
		List<BigIntegerFraction>[] tmpMatrix = getMatrixCopy();

		for (int row = 0; row < _rows; row++)
		{
			for (int column = 0; column < _columns; column++)
			{
				// a[chosenRow][j] / a[chosenRow][chosenColumn]
				BigIntegerFraction tmp = _matrix[chosenRow].get(column).divide(_matrix[chosenRow].get(chosenColumn));
				if (row == chosenRow)
				{
					tmpMatrix[row].set(column, tmp);
				}
				else
				{
					// a[i][j] - a[i][chosenColumn] / a[chosenRow][newColumn] * a[chosenRow][j]
					tmpMatrix[row].set(column, _matrix[row].get(column).subtract(_matrix[row].get(chosenColumn).multiply(tmp)));
				}
			}
		}
		_matrix = tmpMatrix;
		_basis[chosenRow] = chosenColumn;
	}

	private List<Integer> v;

	protected void workWithNegatives()
	{
		if (v.size()>0)
		{
			int i,j;
			for (i=0;i<v.size();i++)
			{
				addColumn2Matrix(v.get(i), BigIntegerFraction.ONE);
				_basis[v.get(i)] = _matrix[i].size()-1;
			}

			//tmpC = c.clone();
			/*
			c = createFractionsArray(n+_rows+1+v.size(), BigIntegerFraction.ZERO);
			for (i=0;i<v.size();i++)
			{
				int index = v.get(i);
				for (j=1;j<basis[index];j++)
					c[j] = c[j].add(_matrix[index].get(j));
				c[0]=c[0].subtract(_matrix[index].get(0));
			}

			doIterations();

			BigIntegerFraction res[] = new BigIntegerFraction[_matrix[0].size()];
			for (i=0;i<_rows;i++)
				res[basis[i]] = _matrix[i].get(0);
			res[0] = BigIntegerFraction.ONE;
			BigIntegerFraction tmp = (BigIntegerFraction)NumberUtilities.scalarProduct(res, c);

			//cout<<res<<endl;

			if (tmp.compareTo(BigIntegerFraction.ZERO) > 0)
				throw new RuntimeException("Could not found first plan.");*/
		}
	}

	private List<BigIntegerFraction>[] getMatrixCopy(Integer... rows2Remove)
	{
		Set<Integer> rows2RemoveSet = new HashSet<Integer>();
		Collections.addAll(rows2RemoveSet, rows2Remove);
		List<BigIntegerFraction>[] tmpMatrix = Arrays.copyOf(_matrix, _rows - rows2RemoveSet.size());
		int currentRow = 0;
		for (int i = 0; i < _rows; i++)
		{
			if (rows2RemoveSet.contains(i))
			{
				continue;
			}
			tmpMatrix[currentRow++] = new ArrayList<BigIntegerFraction>(_matrix[i]);
		}
		return tmpMatrix;
	}

	private void printMatrix()
	{
		if (!_debug)
			return;
		int length = 0;
		for (int i = 0; i < _rows; i++)
			for (int j = 0; j < _columns; j++)
			{
				length = Math.max(length, _matrix[i].get(j).toString().length() + 1);
			}
		for (int i = 0; i < _rows; i++)
		{
			for (int j = 0; j < _columns; j++)
			{
				System.out.print(StringUtilities.toString(_matrix[i].get(j).toString(), length));
			}
			System.out.println();
		}
	}

	private List<Integer> getFakeBasisColumns()
	{
		List<Integer> result = new ArrayList<Integer>();
		for (int index = 0; index < _basis.length; index++)
			if (_basis[index] >= _startFakeColumn)
			{
				result.add(index);
			}
		return result;
	}

	private boolean isAllColumnValuesZero(Collection<Integer> indexes, int column)
	{
		for (Integer index : indexes)
			if (!BigIntegerFraction.ZERO.equals(_matrix[index].get(column)))
				return false;
		return true;
	}
}
